package tests;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;

import trees.*;
import junit.framework.TestCase;


public class BinaryTreeTest extends TestCase {

	private static int testSize = 500000;
	BinaryTree<Integer> int_tree;
	BinaryTree<String> str_tree;
	
	public void testConstructor() {
		int_tree = new BinaryTree<Integer>();
		str_tree = new BinaryTree<String>();
	}

	public void testInsert() {
		int_tree = new BinaryTree<Integer>();
		int_tree.insert(3);
		int_tree.insert(5);
		int_tree.insert(4);
		int_tree.insert(4);
		assertEquals(4, int_tree.size());
		assertEquals(null, int_tree.remove(2));
		assertEquals(new Integer(4), int_tree.remove(4));	// recognize 4 insertion
		assertEquals(new Integer(4), int_tree.remove(4));	// recognize double 4 values
		assertEquals(null, int_tree.remove(4)); 			// doesn't contain any more 4's
		assertEquals(new Integer(3), int_tree.remove(3));	// recognize lesser value
		assertEquals(new Integer(5), int_tree.remove(5));	// recognize greater value
	}

	public void testSize() {
		int_tree = new BinaryTree<Integer>();
		for (int size = 0; size < 200; size ++) {
			int_tree = new BinaryTree<Integer>();
			for (int i = 0; i < size; i ++)
				int_tree.insert((int)(Math.random() * 45));
			assertEquals(size, int_tree.size());
		}		
	}
	
	public void testDepth() {
		
	}

	/**
	 * Tests that the iterator returns all sorted elements.
	 */
	public void testIterator() {
		Random rand;
		Iterator<Integer> output;
		int[] insertedVals;
		int toInsert;

		rand = new Random();
		int_tree = new BinaryTree<Integer>();
		insertedVals = new int[testSize];

		/* empty iterator case */
		for (Integer i : int_tree.iterator())
			fail("empty iterator fail");
		
		for (int i = 0; i < testSize; i ++) {
			toInsert = rand.nextInt(200000000);
			insertedVals[i] = toInsert;
			int_tree.insert(toInsert);
		}
		
		Arrays.sort(insertedVals);
		output = int_tree.iterator().iterator();
		
		for (int i = 0; i < testSize; i ++) {
			assertEquals(insertedVals[testSize - i - 1], (int)output.next());			
		}
	}
	
}
